package graph.impl;

import edu.princeton.cs.introcs.In;
import edu.princeton.cs.introcs.StdOut;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

public class StringGraphBFP {
	private Map<String,Boolean> visited = null;
	private StringGraph graph = null;
	private Map<String,String> previousEdgeMap = null;
	private Queue<String> vertexQueue = null;
	
	public StringGraphBFP(StringGraph graph) {
		visited = new HashMap<String,Boolean>();
		this.graph = graph;
		vertexQueue = new LinkedList<String>();
		previousEdgeMap = new HashMap<String,String>();
	}
	
	public void bfs(String source){		
		vertexQueue.offer(source);		
		previousEdgeMap.put(source,source);
		while(!vertexQueue.isEmpty()){
			String vertex = vertexQueue.remove();
			if(!visited.containsKey(vertex)){
				visited.put(vertex, Boolean.TRUE);
				Set<String> edges = graph.getEdges(vertex);
				for(String edge : edges){
					if(!vertexQueue.contains(edge))	{
						vertexQueue.offer(edge);		
					}
					if(!previousEdgeMap.containsKey(edge)){
						previousEdgeMap.put(edge,vertex);
					}
				}
			}			
		}	
	}
	
	public boolean hasPathTo(String source, String dest){
		return visited.get(dest);
	}
	
	public Stack<String> pathTo(String source, String dest){
		Stack<String> stack = new Stack<String>();
		String vertex = dest;
		while(!vertex.equals(source)){
			stack.push(vertex);
			vertex = previousEdgeMap.get(vertex);
		}
			stack.push(vertex);
			return stack;
	}
	public static void main(String[] args) {
		In in = new In(args[0]);
		String source = args[1];
		StringGraph stringGraph = new StringGraph(in);
		StringGraphBFP bfp = new StringGraphBFP(stringGraph);
		
		bfp.bfs(source);
		if(bfp.visited.size() == stringGraph.vertexCount) {
			StdOut.println(bfp.visited);
		}
		
		Set<String> vertices = stringGraph.getVertices();
		for(String vertex : vertices){
			if(bfp.hasPathTo(source, vertex)){
				StdOut.print(source + " to " + vertex + " :: ");
				Stack<String> paths = bfp.pathTo(source, vertex);				
				while(!paths.isEmpty()){
					String path = paths.pop();
					if(path.equals(source)){
						StdOut.print(path);
					}	else	{
						StdOut.print(" - " + path);
					}
				}
				StdOut.println();
			}
		}
		// TODO Auto-generated method stub

	}

}
